/* 
 * Reverse Nodes in k-Group
 * Given a linked list, reverse the nodes of a linked list k at a time and return its modified list
 * For example, Given this linked list: 1->2->3->4->4
 * For k = 2, you should return: 2->1->4->3->5
 * For k = 3, you should return: 3->2->1->4->5
 */

#include "../../func.h"

ListNode *reverseKGroup(ListNode *head, int k)
{
    if (head == nullptr || head->next == nullptr || k < 2)
        return head;

    ListNode *next_group = head;
    for (int i = 0; i < k; ++i)
    {
        if (next_group)
            next_group = next_group->next;
        else
            return head;
    }

    ListNode *new_next_group = reverseKGroup(next_group, k);
    ListNode *prev = nullptr, *cur = head;
    while (cur != next_group)
    {
        ListNode *next = cur->next;
        cur->next = prev ? prev : new_next_group;
        prev = cur;
        cur = next;
    }
    return prev;
}


/*
ListNode *reverseKGroup2(ListNode *head, int k)
{
    if (nullptr == head || nullptr == head->next || k < 2)
        return head;
    ListNode dummy(-1);
    dummy.next = head;

    for (ListNode *prev = &dummy, *end = head; end; end = prev->next)
    {
        for (int i = 1; i < k && end; ++i)
        {
            end = end->next;
        }
        if (nullptr == end)
            break;

        prev = reverse(prev, prev->next, end);
    }
}
*/